/*
 * @lc app=leetcode.cn id=509 lang=cpp
 *
 * [509] 斐波那契数
 *
 * 方法1：递归求解 + 动态规划
 * - F(n) = F(n - 1) + F(n - 2)
 *
 * 方法2：自底向上非递归求解
 */

#include <vector>

// @lc code=start
class Solution
{
public:
    int fib(int n)
    {
        if (n == 0)
            return 0;
        std::vector<int> fibDP(n + 1);
        fibDP[1] = 1;
        for (int i = 2; i <= n; i++)
            fibDP[i] = fibDP[i - 1] + fibDP[i - 2];

        return fibDP[n];
    }
};
// @lc code=end
